node complexity
Bounds on the complexity of recurrent neural network implementations of finite state machines
In this paper the efficiency of recurrent neural network implementa(cid:173) tions of m-state finite state machines will be explored. Specifically, it will be shown that the node complexity for the unrestricted case can be bounded above by 0 ( fo) . It will also be shown that the node complexity is 0 (y'm log m) when the weights and thresholds are restricted to the set {-I, I}, and 0 (m) when the fan-in is re(cid:173) stricted to two. Matching lower bounds will be provided for each of these upper bounds assuming that the state of the FSM can be encoded in a subset of the nodes of size rlog m 1.
Bounds on the complexity of recurrent neural network implementations of finite state machines
Although there are many ways to measure efficiency, we shall be concerned with node complexity, which as its name implies, is a calculation of the required number of nodes. Node complexity is a useful measure of efficiency since the amount of resources required to implement or even simulate a recurrent neural network is typically related to the number of nodes. Node complexity can also be related to the efficiency of learning algorithms for these networks and perhaps to their generalization ability as well. We shall focus on the node complexity of recurrent neural network implementations of finite state machines (FSMs) when the nodes of the network are restricted to threshold logic units.
Bounds on the complexity of recurrent neural network implementations of finite state machines
Although there are many ways to measure efficiency, we shall be concerned with node complexity, which as its name implies, is a calculation of the required number of nodes. Node complexity is a useful measure of efficiency since the amount of resources required to implement or even simulate a recurrent neural network is typically related to the number of nodes. Node complexity can also be related to the efficiency of learning algorithms for these networks and perhaps to their generalization ability as well. We shall focus on the node complexity of recurrent neural network implementations of finite state machines (FSMs) when the nodes of the network are restricted to threshold logic units.
Bounds on the complexity of recurrent neural network implementations of finite state machines
In this paper we shall be concerned with Mealy machines, although our approach can easily be extended to other formulations to yield equivalent results.